package jmine.tec.utils.dependency;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import jmine.tec.utils.UtilsMessages;
import bancosys.tec.utils.UtilsComponentRuntimeException;

/**
 * Representa um grafo de dependencias que admite ordem topológica. Essa representação não permite ciclos.
 * 
 * @author piercio
 * @param <T> o tipo das dependências.
 */
public class DependencyGraph<T> {

    private final Map<T, Node> nodes;

    private final Node initialNode = new Node(null);

    private List<? extends T> order = null;

    /**
     * Contrutor.
     */
    public DependencyGraph() {
        this.nodes = new LinkedHashMap<T, Node>();
        this.nodes.put(null, this.initialNode);
    }

    /**
     * Adiciona os valores ao grafo de dependência e verifica se há ciclos. Lança UtilsComponentRuntimeException caso haja ciclos no grafo.
     * 
     * @param values uma lista de valores em ordem parcial de dependência, ou seja, na lista (A, B, C), C depende de B e B depende de A.
     */
    public void addValues(Collection<? extends T> values) {
        this.addValuesSkipCheck(values);
        if (!values.isEmpty()) {
            this.generateTopologicalOrder();
        }
    }

    /**
     * Adiciona os valores ao grafo de dependência. Este método não verifica a ocorrência de ciclos.
     * 
     * @param values uma lista de valores em ordem parcial de dependência, ou seja, na lista (A, B, C), C depende de B e B depende de A.
     */
    public void addValuesSkipCheck(Collection<? extends T> values) {
        Node currentNode = this.initialNode;
        for (T value : values) {
            if (value == null) {
                continue;
            }
            Node nextNode = this.nodes.get(value);
            if (nextNode == null) {
                nextNode = new Node(value);
                this.nodes.put(value, nextNode);
            }
            currentNode.addDependent(nextNode);
            currentNode = nextNode;
        }
        this.order = null;
    }

    /**
     * Gera uma ordem topológica a partir do grafo de dependências com ordens parciais. Lança UtilsComponentRuntimeException caso haja
     * ciclos no grafo.
     */
    private void generateTopologicalOrder() {
        Collection<Node> values = this.nodes.values();
        Node start = this.initialNode;

        for (Node node : values) {
            node.resetEntryLevel();
        }
        for (Node node : values) {
            for (Node dependent : node.getDependents()) {
                dependent.incrementEntryLevel();
            }
        }

        LinkedList<T> list = new LinkedList<T>();
        List<Node> free = new ArrayList<Node>();
        free.add(start);

        while (!free.isEmpty()) {
            Node node = free.remove(0);
            if (node.getValue() != null) {
                list.add(node.getValue());
            }

            for (Node dependent : node.getDependents()) {
                if (dependent.getEntryLevel() <= 0) {
                    throw new UtilsComponentRuntimeException(UtilsMessages.DEPENDENCY_CYCLE_DETECTED.create());
                }
                dependent.decrementEntryLevel();
                if (dependent.getEntryLevel() == 0) {
                    free.add(dependent);
                }
            }
        }

        if (list.size() != this.nodes.size() - 1) {
            throw new UtilsComponentRuntimeException(UtilsMessages.DEPENDENCY_CYCLE_DETECTED.create());
        }

        this.order = list;
    }

    /**
     * Devolve a ordem topológica do grafo de dependências.
     * 
     * @return a ordem topológica do grafo de dependências.
     */
    public List<? extends T> getTopologicalOrder() {
        if (this.order == null) {
            this.generateTopologicalOrder();
        }
        return this.order;
    }

    /**
     * Representa um nó do grafo de dependências.
     * 
     * @author piercio
     */
    private class Node {

        private final T value;

        private final Set<Node> dependents;

        private int entryLevel;

        /**
         * Construtor.
         * 
         * @param value o conteúdo do nó.
         */
        Node(T value) {
            this.value = value;
            this.dependents = new LinkedHashSet<Node>();
        }

        /**
         * Devolve o conteúdo do nó.
         * 
         * @return o conteúdo do nó.
         */
        T getValue() {
            return this.value;
        }

        /**
         * Adiciona um nó dependênte deste nó.
         * 
         * @param dependent o outro nó que depende deste nó.
         */
        void addDependent(Node dependent) {
            this.dependents.add(dependent);
        }

        /**
         * Retorna todos os nó que dependem deste nó.
         * 
         * @return todos os nó que dependem deste nó.
         */
        Set<Node> getDependents() {
            return this.dependents;
        }

        /**
         * Devolve o número de nós que este nó depende.
         * 
         * @return o número de nós que este nó depende.
         */
        int getEntryLevel() {
            return this.entryLevel;
        }

        /**
         * Força nivel de entrada para 0.
         */
        void resetEntryLevel() {
            this.entryLevel = 0;
        }

        /**
         * Incrementa o nivel de entrada.
         */
        void incrementEntryLevel() {
            this.entryLevel++;
        }

        /**
         * Decrementa o nivel de entrada.
         */
        void decrementEntryLevel() {
            this.entryLevel--;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((this.value == null) ? 0 : this.value.hashCode());
            return result;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            @SuppressWarnings("unchecked")
            Node other = (Node) obj;
            if (this.value == null) {
                if (other.value != null) {
                    return false;
                }
            } else if (!this.value.equals(other.value)) {
                return false;
            }
            return true;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public String toString() {
            return (this.value == null) ? "" : this.value.toString();
        }

    }

}
